前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

• 1 <= s1.length, s2.length <= 10^4
• s1 and s2 consist of lowercase English letters.

Think

給兩個string(s1&s2)，如果s1的所有排列組合中有出現在s2中，救回傳True；如果沒有，則回傳否。

• 首先判斷是否s1的長度能包含在s2中
• 再來，先初始化s1_dict與s2_dict~
  • 這邊s2_dict存入的字母出現頻率是只有s2從index: 0開始到跟s1一樣長度的substring
• 比較s1_dict和s2_dict中有哪些字母的出現頻率是一樣的~有的話，check+1
• Init check完就先檢查一下check是不是26，因為有可能第一個s2的window中就出現s1的其中一種排列組合。

Main while loop

• 因為ptr為0的時候，已經先處理完了，所以while每次的第一行就先移動ptr到下一格(移動window)。

• MINUS Part:

  • 因為每次只移動一格，所以前一個的ptr的字母一定會不見，所以s2_dict先把前一個的ptr的字母的出現頻率-1
  • 接著，我們才來判斷s1_dict和s2_dict中ptr-1的字母的出現頻率是否相同，相同的話，check+1
  • 不同的話，另外再判斷原來s1_dict和s2_dict中ptr-1的字母的出現頻率是否相同，相同的話，check-1；不同的話，因為本來check就減過就不用管他了~

• PLUS Part:

  • 同樣地，因為每次只移動一格，所以一定會增加ptr+len(s1)的字母，所以s2_dict先把ptr+len(s1)的字母的出現頻率+1
  • 接著，跟上面一樣，我們才來判斷s1_dict和s2_dict中ptr-1的字母的出現頻率是否相同，相同的話，check+1
  • 不同的話，另外再判斷原來s1_dict和s2_dict中ptr-1的字母的出現頻率是否相同，相同的話，check-1；不同的話，因為本來check就減過就不用管他了~

• Return Part:

  • 如果某一次check是26，表示這次s2的window是s1的排列組合，回傳True。
  • 如果ptr+len(s1)已經大於len(s2)，表示已經跑完啦~
  • while都跑完還是沒有，就直接回傳False~

• 基本上一樣~

Code

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int ptr = 0;
        unordered_map<char, int> s1_dict;
        unordered_map<char, int> s2_dict;
        int check = 0;
        
        if(s1.length() > s2.length()){
            return false;
        }
        
        for(int index=0 ; index<s1.length() ; index++){
            s1_dict[s1[index]]++;
            s2_dict[s2[ptr+index]]++;
        }
        
        for(char letter='a' ; letter<='z' ; letter++){
            // cout << letter << endl;
            if(s1_dict[letter] == s2_dict[letter]){
                check++;
            }
        }
        
        // cout << "Init Check: " << check << endl;
        
        if(check == 26){
            return true;
        }
        
        while(ptr + s1.length() < s2.length()){
            ptr++;
            
            // cout << "\nWindow: " << s2.substr(ptr, s1.length()) << endl;
            
            // MINUS:
            s2_dict[s2[ptr-1]]--;
            if(s1_dict[s2[ptr-1]] == s2_dict[s2[ptr-1]]){
                check++;                
            } else {
                if(s1_dict[s2[ptr-1]] == s2_dict[s2[ptr-1]] + 1){
                    check--;
                }
            }
            // cout << "After MINUS=> \nCheck: " << check << endl;
                
            // PLUS:
            s2_dict[s2[ptr+s1.length()-1]]++;
            if(s1_dict[s2[ptr+s1.length()-1]] == s2_dict[s2[ptr+s1.length()-1]]){
                check++;                
            } else {
                if(s1_dict[s2[ptr+s1.length()-1]] == s2_dict[s2[ptr+s1.length()-1]] - 1){
                    check--;
                }
            }
            
            // cout << "After PLUS=> \nCheck: " << check << endl;
                
            if(check == 26){
                return true;
            }
                
        }
        return false;
    }
        
};

Submission

• 用到比較不一樣的東西反而只是在cout印東西的時候XD，本來在Python的時候是用s2[ptr:ptr+len(s1)]，但在C++改用s2.substr(ptr, s1.length())，ptr是想擷取的字串的起始點，而s1.length()就是想擷取的子字串的長度~

今天就到這邊啦~
大家明天見